﻿// heap_sort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>

void swap(int* p, int x, int y)
{
	// 这里不含等号，避免交换数据
	if (p[x] < p[y])
	{
		int tmp = p[x];
		p[x] = p[y];
		p[y] = tmp;
	}
}
// 交换父子节点
void swap_tree(int* p, int curIndex, int maxIndex)
{
	// 左节点index
	int l = (curIndex << 1) + 1; // 移位操作要打括号，优先级比加法低--搞了好一会儿才发现
	// 有节点index
	int r = l + 1;	
	
	// 没有子节点
	if (maxIndex < l)
	{
		printf("out:maxIndex:%d %d l:%d\n", maxIndex, curIndex,l);
		return;
	}

	// 至少有一个节点
	// 先交换左节点
	swap(p, curIndex, l);

	// 还有右子节点
	if (maxIndex >= r)
	{
		swap(p, curIndex, r);
	}
}

// 使用递归实现
void heap_sort(int* p, int maxIndex)
{
	// 最后一个数字默认有序
	if (maxIndex < 1)
	{
		return;
	}

	// 交换父与子节点,选择最大或者最小的放在父节点
	// 只需要从树倒数第二排开始往上遍历
	// 因为知道树的父节点，知道树的子节点index
	// 关系p_index = (l_index - 1) / 2  
	// 关系p_index = (r_index - 1) >> 1 右移或者除2效果一样
	int sortIndex = (maxIndex - 1) >> 1;
	for (int i = sortIndex; i >= 0; --i)
	{
		// 检查子节点与父节点大小并重新赋值
		swap_tree(p, i, maxIndex);
	}

	// 堆顶排好后已经是最大或者最小值，只需传入未排好序的数组首地址
	heap_sort(++p, --maxIndex);
}

void printArr(int*p, int len)
{
	printf("len: %d --", len);
	for (int i = 0; i < len; ++i)
	{
		printf(" %d", p[i]);
	}
	printf("\n");
}

// 使用for循环实现
void heap_sort_for(int* p, int maxIndex)
{
	for (int index = maxIndex; index > 0; --index, ++p)
	{
		int sortIndex = (index - 1) >> 1;
		for (int i = sortIndex; i >= 0; --i)
		{
			// 检查子节点与父节点大小并重新赋值
			swap_tree(p, i, index);
		}
	}
}

int main()
{
	int p[] = {6, 65,8,8,9,8,7,5 ,777,67,878};
	int maxIndex = sizeof(p) / sizeof(p[0]) - 1; 
	// 使用递归实现
	//heap_sort(p, maxIndex);
	// 使用for循环
	heap_sort_for(p, maxIndex);
	printArr(p, maxIndex);
	for (;;)
	{
	}
}

